package leetcode.code;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.IDebug58;
import leetcode.helper.HelpDebug;
import leetcode.helper.MaxDebug;

public class Solution31 implements IDebug, IDebug58 {

	public void nextPermutation(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return;
		}
		boolean asc = true;
		boolean desc = true;
		for (int i = 1; i < len; i++) {
			if (nums[i] < nums[i - 1]) {
				asc = false;
			} else if (nums[i] > nums[i - 1]) {
				desc = false;
			}
		}
		if (len == 2 && asc) {
			int temp = nums[0];
			nums[0] = nums[1];
			nums[1] = temp;
			return;
		}
		if (desc) {
			Arrays.sort(nums);
			return;
		}
		Integer[] left = new Integer[2];
		for (int i = len - 1; i > 0; i--) {
			if (left[0] != null && i < left[0]) {
				break;
			}
			for (int j = i - 1; j >= 0; j--) {
				if (nums[j] < nums[i]) {
					if (left[0] == null || j > left[0]) {
						left[0] = j;
						left[1] = i;
					}
					break;
				}
			}
		}
		if (left[0] == null) {
			Arrays.sort(nums);
			return;
		}
		int temp = nums[left[0]];
		nums[left[0]] = nums[left[1]];
		nums[left[1]] = temp;
		Arrays.sort(nums, left[0] + 1, nums.length);
	}

	@Override
	public void debug1() {
		String str = "[1,2,3]";
		int[] nums = HelpDebug.str2array3(str);
		String str1 = "[1,3,2]";
		int[] e = HelpDebug.str2array3(str1);
		this.nextPermutation(nums);
		HelpDebug.compare(e, nums);
	}

	@Override
	public void debug2() {
		String str = "[3,2,1]";
		int[] nums = HelpDebug.str2array3(str);
		String str1 = "[1,2,3]";
		int[] e = HelpDebug.str2array3(str1);
		this.nextPermutation(nums);
		HelpDebug.compare(e, nums);
	}

	@Override
	public void debug3() {
		String str = "[1,1,5]";
		int[] nums = HelpDebug.str2array3(str);
		String str1 = "[1,5,1]";
		int[] e = HelpDebug.str2array3(str1);
		this.nextPermutation(nums);
		HelpDebug.compare(e, nums);
	}

	@Override
	public void debug4() {
		String str = "[1]";
		int[] nums = HelpDebug.str2array3(str);
		String str1 = "[1]";
		int[] e = HelpDebug.str2array3(str1);
		this.nextPermutation(nums);
		HelpDebug.compare(e, nums);
	}

	public static void main(String[] args) {
		Solution31 so = new Solution31();
//		so.debug2();
		MaxDebug.debug14(so);
		MaxDebug.debug58(so);
	}

	@Override
	public void debug5() {
		String str = "[1,2,7,2,6,5,3]";
		int[] nums = HelpDebug.str2array3(str);
		String str1 = "[1,2,7,3,2,5,6]";
		int[] e = HelpDebug.str2array3(str1);
		this.nextPermutation(nums);
		HelpDebug.compare(e, nums);
	}

	@Override
	public void debug6() {
		String str = "[1,2,7,2,5,6,3]";
		int[] nums = HelpDebug.str2array3(str);
		String str1 = "[1,2,7,2,6,3,5]";
		int[] e = HelpDebug.str2array3(str1);
		this.nextPermutation(nums);
		HelpDebug.compare(e, nums);
	}

	@Override
	public void debug7() {
		String str = "[1,2]";
		int[] nums = HelpDebug.str2array3(str);
		String str1 = "[2,1]";
		int[] e = HelpDebug.str2array3(str1);
		this.nextPermutation(nums);
		HelpDebug.compare(e, nums);
	}

	@Override
	public void debug8() {
		// TODO Auto-generated method stub

	}

}
